package org.example.sword2offer.primary;

/**
 * @author: lynn
 * @Descript: 二叉搜索树与双向链表
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
 * 要求不能创建任何新的结点，只能调整树中结点指针的指向。
 * @date: 2021/3/13 9:14
 * @version: 1.0
 */
public class Q26_Convert_H {

    public static TreeNode leftHead = null;
    public static TreeNode rightHead = null;

    public static void main(String[] args) {
        TreeNode root=new TreeNode(8);
        root.left=new TreeNode(4);
        root.right=new TreeNode(10);
        root.left.left=new TreeNode(2);
        root.left.right=new TreeNode(6);
        root.right.left=new TreeNode(9);
        root.right.right=new TreeNode(13);

        //findLeft(Convert(root));
        Convert(root);
    }
    public static TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) return  null;

        Convert(pRootOfTree.left);

        if (leftHead == null) {
            leftHead = pRootOfTree;
            rightHead = pRootOfTree;
        }
        else {
            rightHead.right = pRootOfTree;
            pRootOfTree.left = rightHead;
            rightHead = pRootOfTree;
        }

        Convert(pRootOfTree.right);

        return leftHead;
    }


/*
    public static TreeNode Convert(TreeNode root) {
        if(root == null){
            return null;
        }
        transform(root);
        return findLeft(root);
    }

    //transform a tree to a double-link list
    public static void transform(TreeNode root){
        if(root == null){
            return;
        }
        TreeNode pre = root.left, next = root.right;
        while(pre != null && pre.right != null){
            pre = pre.right;
        }
        while(next != null && next.left != null){
            next = next.left;
        }

        transform(root.left);
        transform(root.right);
        //asume the left and right has transformed and what's remaining is link the root
        root.left = pre;
        if(pre != null){
            pre.right = root;
        }
        root.right = next;
        if(next != null){
            next.left = root;
        }
    }

    private static TreeNode findLeft(TreeNode root) {
        while (root.left != null)
            root = root.left;
        return root;
    }*/
    private static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val=val;
        }
    }
}
